package Util.Map;

import java.io.Serializable;
import java.util.Objects;
import java.util.Set;

public class HashMapInJDK7<K, V> extends AbstractMap<K, V> implements Map<K, V>, Cloneable, Serializable {

    /**
     * 默认初始容量 - 必须是2的幂
     */
    static final int DEFAULT_INITIAL_CAPACITY = 16;
    /**
     * 最大容量
     */
    static final int MAXIMUM_CAPACITY = 1 << 30;
    /**
     * 默认负载因子
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    /**
     * 当表没有膨胀时, 要共享的空表实例
     */
    static final Entry<?, ?>[] EMPTY_TABLE = {};

    // Transient 表明该数据不参与序列化
    // 1, 假设HashMap中的存储数据的数组还有很多的空间没有被使用, 没有被使用到的空间被序列化没有意义。所以下文会有手动使用 writeObject() 方法, 只序列化实际存储元素的数组
    // 2, 不同的虚拟机对于相同 hashCode 产生的 Code 值可能是不一样的, 如果使用默认序列化, 则反序列化后, 元素的位置和之前的是保持一致的, 
    //          可是由于 hashCode 的值不一样了, 那么后续看到的定位函数 indexOf（）返回的元素下标就会不同, 其结果会出差错。

    /**
     * 根据需要调整表的大小。长度必须是2的次幂
     */
    transient Entry<K, V>[] table = (Entry<K, V>[]) EMPTY_TABLE;
    /**
     * HashMap中包含的键-值映射的数目
     */
    transient int size;

    /**
     * 扩容的临界值(容量 * 加载因子) 即 可以存放的最大量
     */
    int threshold;

    /**
     * 哈希表的负载因子
     */
    final float loadFactor;

    /**
     * 每进行一次集合的元素修改, 就会进行加1 (但是元素的替换并不算集合元素修改之内)
     * 由于HashMap非线程安全, 用于快速失败
     */
    transient int modCount;

    /**
     * Map容量的默认阈值, 超过该阈值, 替代哈希用于字符串键
     * 替代哈希可降低由于字符串键的哈希代码计算较弱而导致的冲突
     * 可以通过定义系统属性来覆盖此值
     */
    static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;

    /**
     * 用于键的哈希码计算上, 用于减少哈希冲突, 通过initHashSeedAsNeeded初始化
     */
    transient int hashSeed = 0;

    /** 保存要在 VM 启动后才能初始化的值 */
    private static class Holder{
        // 可切换到替代哈希的表容量
        static final int ALTERNATIVE_HASHING_THRESHOLD;
        static {
            //源码部分已废弃, 静态代码块主要功能是为ALTERNATIVE_HASHING_THRESHOLD赋初始值,这里我简单赋一下值
            ALTERNATIVE_HASHING_THRESHOLD = ALTERNATIVE_HASHING_THRESHOLD_DEFAULT;

            /* 源代码
            String altThreshold = java.security.AccessController.doPrivileged(
                    new sun.security.action.GetPropertyAction(
                            "jdk.map.althashing.threshold"));

            int threshold;
            try {
                threshold = (null != altThreshold)
                        ? Integer.parseInt(altThreshold)
                        : ALTERNATIVE_HASHING_THRESHOLD_DEFAULT;

                // disable alternative hashing if -1
                if (threshold == -1) {
                    threshold = Integer.MAX_VALUE;
                }

                if (threshold < 0) {
                    throw new IllegalArgumentException("value must be positive integer.");
                }
            } catch(IllegalArgumentException failed) {
                throw new Error("Illegal value for 'jdk.map.althashing.threshold'", failed);
            }

            ALTERNATIVE_HASHING_THRESHOLD = threshold;
             */
        }
    }



    public HashMapInJDK7(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0) {
            throw new IllegalArgumentException("Illegal initial capacity: " +
                    initialCapacity);
        }
        if (initialCapacity > MAXIMUM_CAPACITY) {
            initialCapacity = MAXIMUM_CAPACITY;
        }
        if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
            throw new IllegalArgumentException("Illegal load factor: " +
                    loadFactor);
        }

        this.loadFactor = loadFactor;
        threshold = initialCapacity;
        init();
    }

    /**
     * 此方法在所有构造函数和伪构造函数（clone, readObject）的初始化HashMap后, 数据插入前调用
     * 如果没有此方法, readObject将需要显式了解子类
     * */
    void init() {
    }

    public HashMapInJDK7(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

    public HashMapInJDK7() {
        this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
    }

    public HashMapInJDK7(Map<? extends K, ? extends V> m) {
        this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
                DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
        inflateTable(threshold);

        putAllForCreate(m);
    }

    /** 向table中添加数据 */
    private void inflateTable(int toSize) {
        // 找到一个最小的2^n, 使得 2^n >= number
        int capacity = roundUpToPowerOf2(toSize);
        //计算扩容值 12
        threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
        //初始化数组长度 16
        table = new Entry[capacity];
        // 延迟初始化哈希掩码值
        initHashSeedAsNeeded(capacity);
    }

    /** 找到一个最小的2^n, 使得 2^n >= number */
    private static int roundUpToPowerOf2(int number) {
        // highestOneBit方法: 找到一个最大的2^n, 使得 2^n <= 传入参数 i （i == 0 则 return 0; i < 0 则 return Integer.MIN_VALUE）
        // (<< 1)运算表示右移1位, 相当于乘以2
        // number - 1 先将原有的数字-1,目的是防止16/32/64..经过(<< 1)后返回32/64/128, 因为16/32/64就是>=16/32/64的最小的2的幂
        // ((number - 1) << 1)的目的是将highestOneBit方法找到的小于number的最大的2^n 变成 2 ^ (n+1)(满足其是>=number的最小的2的幂)
        return number >= MAXIMUM_CAPACITY ? MAXIMUM_CAPACITY
                : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
    }

    /** 初始化hashSeed */
    final boolean initHashSeedAsNeeded(int capacity) {
        // sun.misc.VM, sun.misc.Hashing已经失效, 避免报错这里直接返回true
        return true;
//        // 源码部分
//        // hashSeed为零 就返回false 不为零 就返回true
//        boolean currentAltHashing = hashSeed != 0;
//        // sun.misc.VM.isBooted()判断VM是否已经加载完成
//        boolean useAltHashing = sun.misc.VM.isBooted() &&
//                (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
//        // 只要useAltHashing为false 那么hashSeed一定为零
//        boolean switching = currentAltHashing ^ useAltHashing;
//        // 如果没有加载完成, 那么就肯定没有hashSeed的值, 所以直接设置hashSeed值为零即可
//        if (switching) {
//            hashSeed = useAltHashing
//                    ? sun.misc.Hashing.randomHashSeed(this)
//                    : 0;
//        }
//        return switching;
    }

    private void putAllForCreate(Map<? extends K, ? extends V> m) {
        for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
            putForCreate(e.getKey(), e.getValue());
        }
    }

    private void putForCreate(K key, V value) {
//        int hash = null == key ? 0 : hash(key);
//        int i = indexFor(hash, table.length);
//
//        /**
//         * Look for preexisting entry for key.  This will never happen for
//         * clone or deserialize.  It will only happen for construction if the
//         * input Map is a sorted map whose ordering is inconsistent w/ equals.
//         */
//        for (Entry<K, V> e = table[i]; e != null; e = e.next) {
//            Object k;
//            if (e.hash == hash &&
//                    ((k = e.key) == key || (key != null && key.equals(k)))) {
//                e.value = value;
//                return;
//            }
//        }
//
//        createEntry(hash, key, value, i);
    }

    final int hash(Object k) {
        // 为了避免报错直接返回JDK 8以后的hash方法， jdk 7 源码部分在下面注释的部分
        int h;
        return (k == null) ? 0 : (h = k.hashCode()) ^ (h >>> 16);
//        // 源码部分
//        // 默认的hashSeed值为0
//        int h = hashSeed;
//        // 如果为String类型，并且hashSeed不等于0，则会调用sun.misc.Hashing.stringHash32()进行hash值计算
//        if (0 != h && k instanceof String) {
//            return sun.misc.Hashing.stringHash32((String) k);
//        }
//
//        h ^= k.hashCode();
//
//        // int是32位的整数,而在进行与操作的时候哈希码只有低16位参与了与运算, 而高16完全不起作用
//        // 导致两个高位不同而低位相同的key算出来的数组下标产生哈希冲突的概率加大
//        // 为了让哈希码的高16位也能参与到运算, 减少哈希碰撞的概率, 因此进行多次扰动，即多次的右移、异或操作, 目的就是为了让HashMap更加散列、随机
//        h ^= (h >>> 20) ^ (h >>> 12);
//        return h ^ (h >>> 7) ^ (h >>> 4);
    }

    /**
     * 该方法返回值就是元素存放在桶数组的下标
     * 要求： 该数组的下标不能越界 && 计算出来的下标要均衡
     * 方法中的位与运算可以保证当前数组不会越界
     * 由于哈希码的任意性, 高位全0低位全1, 故结果是均衡的
     * 不用取模运算而用与运算, 因为与运算要快得多
     */
    static int indexFor(int h, int length) {
        // 位与运算, 保证当前数组不会越界, 减1是为了让高位全是0, 低位全是1(因为 length - 1 == 2 ^ n - 1), 保证 index 的范围在[0, length - 1], 不会越界
        return h & (length - 1);
    }

    @Override
    public int size() {return size;}

    @Override
    public boolean isEmpty() {return size == 0;}

    static class Entry<K, V> implements Map.Entry<K, V>{
        final K key;
        V value;
        Entry<K, V> next;
        int hash; //不是k.hashCode()方法返回的值, 而是hash()方法的返回值

        Entry(int h, K k, V v, Entry<K, V> n) {
            value = v;
            next = n;
            key = k;
            hash = h;
        }

        @Override
        public K getKey() {return key;}

        @Override
        public V getValue() {return value;}

        @Override
        public V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }

        @Override
        public final boolean equals(Object o){
            return o instanceof Map.Entry<?, ?> e
                    && Objects.equals(getKey(), e.getKey())
                    && Objects.equals(getValue(), e.getValue());
        }

        @Override
        public final int hashCode(){
            return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
        }

        @Override
        public final String toString() {
            return getKey() + "=" + getValue();
        }

    }

    @Override
    public Set<Map.Entry<K, V>> entrySet() {
        return null;
    }
}
